package leetcode每日一题.leetcode20213;

/**
 * 1. 问题描述
 *      计算二维数组的任意方块和
 *
 * 2. 算法分析
 *      1. 暴力
 *
 *      2. 一维前缀和
 *
 *      3. 二维前缀和
 *
 * 3. 代码实现
 */
@SuppressWarnings("all")
public class Q002_二维区域和检索_矩阵不可变 {
    /**
     * 暴力法实现
     */
    class NumMatrix1 {

        int[][] temp;

        public NumMatrix1(int[][] matrix) {
            temp = matrix;
        }

        public int sumRegion(int row1, int col1, int row2, int col2) {
            int res = 0;
            for(int i = row1; i <= row2; i++) {
                for(int j = col1; j <= col2; j++) {
                    res += temp[i][j];
                }
            }
            return res;
        }
    }

    /**
     * 一维前缀和
     * 行前缀和进行优化，主要的操作时间在初始化，之后求出当前矩阵的任意方块和可以控制在方块的行数之差
     * 暴力是扫描需要求出的每个元素，而行前缀将所求的二维方块看成有行组成的矩阵，对每行的和控制在O(1)
     * 的复杂度内，所以整个算法的复杂度由行的数量决定
     * 编写代码的时候注意边界问题，在设置前缀二维矩阵的时候我们通常设置一个带有哨兵的二维矩阵，即比原
     * 矩阵大一圈的二维数组，可以有效的避免数组越界问题
     */
    class NumMatrix2 {

        int[][] pre;  // 记录二维矩阵的行前缀和

        public NumMatrix2(int[][] matrix) {
            int row = matrix.length;
            if(row == 0) {
                return;
            }
            int col = matrix[0].length;
            if(col == 0) {
                return;
            }
            pre = new int[row][col+1];
            // 初始化前缀哨兵
            for(int i = 0; i < row; i++) {
                pre[i][0] = 0;
            }
            // 初始化前缀和矩阵 注意列从1开始
            for(int i = 0; i < row; i++) { // 记录第i行的前缀和
                pre[i][1] = matrix[i][0];
                for(int j = 1; j < col; j++) {
                    pre[i][j+1] = pre[i][j] + matrix[i][j];
                }
            }
        }

        public int sumRegion(int row1, int col1, int row2, int col2) {
            int res = 0;
            for(int i = row1; i <= row2; i++) {
                res += (pre[i][col2+1] - pre[i][col1]);
            }
            return res;
        }
    }

    /**
     * 二维前缀和   时间复杂度控制在O(1)内
     * 前缀和的二维递推式子：f(i,j)=f(i−1,j)+f(i,j−1)−f(i−1,j−1)+matrix[i][j]
     * 其中f(i,j)表示前i行j列的方块和
     */
    class NumMatrix3{

        int[][] pre;  // 二维前缀和

        public NumMatrix3(int[][] matrix) {
            int row = matrix.length;
            if(row > 0) {
                int col = matrix[0].length;
                pre = new int[row+1][col+1];
                for(int i = 0; i < row; i++) {
                    for(int j = 0; j < col; j++) {
                        pre[i+1][j+1] = pre[i][j+1] + pre[i+1][j] - pre[i][j] + matrix[i][j];
                    }
                }
            }
        }

        public int sumRegion(int row1, int col1, int row2, int col2) {
            return pre[row2+1][col2+1] - pre[row2+1][col1] - pre[row1][col2+1] + pre[row1][col1];
        }
    }
}
